package com.alex.space.commons;

import org.apache.commons.lang3.RandomUtils;
import org.apache.commons.lang3.time.StopWatch;

/**
 * @author Alex
 *         Created by Alex on 2017/12/27.
 */
public class SearchUtils {

    private static final int ARRAY_SIZE = 10;
    private static StopWatch stopWatch = new StopWatch();

    public static void main(String[] args) {

        int[] num = generateDistinctRandomArray();
        System.out.println("Init array:");
        printArray(num);

        stopWatch.start();

        int r = randomizedSelect(num, 0, num.length - 1, 5);

        stopWatch.stop();

        System.out.println("time is " + stopWatch.getTime());

        System.out.println("r is " + r);

    }

    public static void printArray(int[] num) {
        for (int n : num) {
            System.out.printf(n + "\t");
        }
        System.out.println();
    }

    public static int[] generateDistinctRandomArray() {
        return generateDistinctRandomArray(ARRAY_SIZE);
    }

    public static int[] generateDistinctRandomArray(int size) {
        int[] num = new int[size];

        for (int i = 0; i < size; i++) {
            num[i] = i + 1;
        }

        for (int i = 0; i < size; i++) {
            int idx = RandomUtils.nextInt(i, size);
            int temp = num[i];
            num[i] = num[idx];
            num[idx] = temp;
        }

        return num;
    }

    /**
     * 随机选择，选择第i小的元素
     */
    public static int randomizedSelect(int[] num, int start, int end, int order) {
        if (start == end) {
            System.out.println("Start equal end " + start);
            return num[start];
        }
        System.out.println("Partition start " + start + "," + end);
        int i = SortUtils.randomPartition(num, start, end);
        printArray(num);
        System.out.println("Partition end " + i);

        int k = i - start + 1;
        if (k == order) {
            return num[i];
        }
        if (k < order) {
            return randomizedSelect(num, i + 1, end, order - k);
        } else {
            return randomizedSelect(num, start, i - 1, order);
        }
    }

}
